# Copyright (c) 2008 Mikael Lind
#
# Permission is hereby granted, free of charge, to any person obtaining a copy
# of this software and associated documentation files (the "Software"), to deal
# in the Software without restriction, including without limitation the rights
# to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
# copies of the Software, and to permit persons to whom the Software is
# furnished to do so, subject to the following conditions:
#
# The above copyright notice and this permission notice shall be included in
# all copies or substantial portions of the Software.
#
# THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
# IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
# FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
# AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
# LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
# OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
# SOFTWARE.


from heapq import heappop, heappush
from itertools import count, izip
from random import randint
from sys import maxint


def divide_box(min_p, max_p, min_size=1, max_count=maxint, randint=randint):
    minint = -maxint - 1
    def item(min_p, max_p):
        key, brk, axis = min((min_x - max_x, randint(minint, maxint), axis)
                             for min_x, max_x, axis
                             in izip(min_p, max_p, count()))
        return key, brk, min_p, max_p, axis
    boxes = [item(tuple(min_p), tuple(max_p))]
    while len(boxes) < max_count:
        key, brk, min_p, max_p, axis = heappop(boxes)
        if -key < 2 * min_size:
            break
        split_x = randint(min_p[axis] + min_size, max_p[axis] - min_size)
        min_q, max_q = list(min_p), list(max_p)
        min_q[axis] = max_q[axis] = split_x
        heappush(boxes, item(min_p, tuple(max_q)))
        heappush(boxes, item(tuple(min_q), max_p))
    return list((min_p, max_p) for key, brk, min_p, max_p, axis in boxes)


def _test(min_p, max_p, min_size, max_count, randint=randint):
    boxes = divide_box(min_p, max_p, min_size, max_count, randint)
    assert len(boxes) <= max_count
    for min_p, max_p in boxes:
        assert all(max_x - min_x >= min_size
                   for min_x, max_x in izip(min_p, max_p))
    if len(boxes) < max_count:
        for min_p, max_p in boxes:
            assert all(max_x - min_x < 2 * min_size
                       for min_x, max_x in izip(min_p, max_p))


if __name__ == '__main__':
    _test((0, 0), (79, 22), 6, 13)
